package org.gushi.algorithm.a03;

public class HeapSort {


    private int[] list;


    public HeapSort(int[] list) {
        this.list = list;
    }

    private int firstLeaf;

    public int[] listSort() {
        /*
         * 完全二叉树
         *
         * 构建大顶堆
         *
         * 数组长度 为偶数 叶子节点数=度为1的节点数+度为2的节点数
         * 数组长度 为奇数 叶子节点数=度为2的节点数+1
         *
         * 完全二叉树的性质：叶子节点数=度为2的节点数+1
         *
         *
         * 找到最后一个非叶子节点
         *
         * 每个节点的左孩子的坐标为2n+1
         * 每个节点的右孩子的坐标为2n+2
         *
         * 每个节点的父节点是
         *
         */
        int notLeaf = (int) Math.floor(list.length / 2) - 1; // 11/2=5
        firstLeaf = notLeaf + 1;
        createHeap(notLeaf);
        System.out.println(list);
        heapSort(list);


        return list;
    }

    private void heapSort(int[] list) {



    }

    public void createHeap(int notLeaf) {
        if (notLeaf < 0) return;

        int node = notLeaf;

        //找到子节点和父节点
//        int parentNode = (int) Math.ceil((node - 1) / 2);//(5-1)/2=2

        int leftNode = (node << 1) + 1; //5*2+1=11
        int rightNode = 0;
        if ((node << 1) + 2 >= list.length) {//5*2+2=12
        } else {
            rightNode = (node << 1) + 2;
        }
        //跟左孩子比
        if (list[node] < list[leftNode]) {
            int temp = list[node];
            list[node] = list[leftNode];
            list[leftNode] = temp;

            //判断左孩子是非叶子节点
            if (leftNode < firstLeaf) {
                createHeap(leftNode);
            }

        }
        //如果存在右孩子 跟右孩子比
        if (rightNode != 0 && list[node] < list[rightNode]) {
            int temp = list[node];
            list[node] = list[rightNode];
            list[rightNode] = temp;
            //判断右孩子是非叶子节点
            if (rightNode < firstLeaf) {
                createHeap(rightNode);
            }

        }

//        //跟父节点比
//        if (list[node] > list[parentNode]) {
//            int temp = list[node];
//            list[node] = list[parentNode];
//            list[parentNode] = temp;
//
//            createHeap(node);
//        }

        System.out.println("节点值："+list[node]);
        //节点
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i]);
            System.out.print(",");
        }

        createHeap(node-1);

    }


}
